class Switch
  attr_accessor :in_up, :in_down, :out_up, :out_down, :ind_bit, :packet_size, :zeropacket
  
  def initialize(add_bit, packet_size)
    @ind_bit = add_bit
    @zeropacket = Array.new packet_size, '0'
  end
  #---------------------------------------------------------
  def run
  #  puts in_up.inspect
  #  puts in_down.inspect
    all_logic = [@in_up[0],@in_down[0],@in_up[@ind_bit],@in_down[@ind_bit] ].join ''

    if all_logic == '0000' or all_logic == '0001' or all_logic == '0010' or all_logic == '0011'
      @out_up = @zeropacket
      @out_down = @zeropacket
    elsif all_logic == '0100' or all_logic == '0110' #down is alive and wants to go up
      @out_down = @zeropacket
      @out_up = @in_down
    elsif all_logic == '0101' or  all_logic == '0111' #down is alive and wants to go down
      @out_up = @zeropacket
      @out_down = @in_down
    elsif all_logic == '1000' or all_logic == '1001' #up is alive and wants to go up
      @out_up = @in_up;
      @out_down = @zeropacket
    elsif  all_logic == '1010'  or all_logic == '1011' #up is alive and wants to go down
      @out_up = @zeropacket
      @out_down = @in_up
    elsif all_logic == '1100' #both alive, collide on up, up wins
      @out_up = @in_up
      @out_down = @zeropacket
    elsif all_logic == '1101' #both alive, straight
      @out_up = @in_up
      @out_down = @in_down
    elsif  all_logic == '1110' #  both alive cross
      @out_up = @in_down
      @out_down = @in_up
    elsif all_logic == '1111' # both alive, collide on down, down wins
      @out_up = @zeropacket
      @out_down = @in_down
    elsif
      throw all_logic
    end
     #puts "(#{all_logic})u[#{@in_up}]d[#{@in_down}]:U[#{@out_up}]D[#{@out_down}]"
  end

end
#==========================================================================================
class Butterfly
  attr_accessor :in_all, :out_all, :data_size, :levels, :offset_size, :packet_size, :sw_mat
  
  def initialize  d_size, lvls, o_size
    @data_size = d_size
    @offset_size = o_size
    @levels = lvls
    @packet_size = 2+@data_size+@levels+@offset_size+@levels
    @sw_mat = {} #build the switches matrix
     (0..@levels-1).each { |level|
     (0..2**(@levels-1)).each  {|port|
        @sw_mat[ [level,2*port] ] = Switch.new 2+@data_size+level, packet_size
      }
    }
    @out_all = []
    
  end
  #---------------------------------------------------------  
  def calculate_next_port curr_level, up_or_down, curr_switch
	port_num = curr_switch + ((up_or_down == :down) ? 1 : 0)
	color = ((port_num &  (1 << curr_level) ) >> curr_level)
	#puts "pn:#{port_num} color: #{color}"
	j = -1 + (1 << curr_level)
	result = -1
	if (color == 0)
	  result = (up_or_down == :up) ? port_num : port_num + j 
	else
	  result = (up_or_down == :up) ? port_num-j : port_num 
	end
	side = (result % 2 == 1) ? :down : :up
	[side, (result % 2 == 1)  ? result-1 : result]
  end
  #---------------------------------------------------------
  def run
    @out_all.clear
    #set return addresses
    port = 0
    @in_all.each {|packet|
      packet[-levels..-1] = sized_int2bin port, levels
      port += 1
    }
    
    #all ins
    (0..2**(@levels-1)-1).each  {|switch|
      sw = @sw_mat[[@levels-1, 2*switch]]
      sw.in_down = @in_all[1+(2*switch)].clone
      sw.in_up = @in_all[2*switch].clone
   }
   
    #all runs
     (@levels-1).downto(1) { |level|
     (0..(2**(@levels-1))-1).each  {|switch|
       currents = @sw_mat[ [level,2*switch] ]
       currents.run
       destination_up = calculate_next_port(level, :up, 2*switch)
       destination_down = calculate_next_port(level, :down, 2*switch)

       if destination_up[0] == :up
        @sw_mat[ [level-1, destination_up[1] ]].in_up = currents.out_up
       else
         @sw_mat[ [level-1, destination_up[1] ]].in_down = currents.out_up
       end
  
       if destination_down[0] == :up
        @sw_mat[ [level-1, destination_down[1] ]].in_up = currents.out_down
       else
         @sw_mat[ [level-1, destination_down[1] ]].in_down = currents.out_down
       end
      }
    }

   #all outs
   (0..2**(@levels-1)-1).each  {|switch|
      sw = @sw_mat[[0, 2*switch]]
      sw.run
      @out_all << sw.out_up
      @out_all << sw.out_down
    }
   
  end
end
#==========================================================================================
#noinspection RubyArgCount
def sized_int2bin num, size=4
  arr = (num.to_s(2).split '').map { |b| b }  #push back lsbs
  (size-arr.size).times { arr << '0'} #padding
  arr.reverse
end
#==========================================================================================
def sized_rand_bin size = 8
  sized_int2bin rand(2**size), size
end
#==========================================================================================
def test_switch
  srand $my_seed
  packet_size = 8
  
  sw = Switch.new 4,packet_size
   (0..15).each { |i|
    logic = sized_int2bin(i)
    tmp = sized_rand_bin(packet_size)
    tmp[0] = i[3]
    tmp[4] = i[1]
    sw.in_up= tmp.clone
    tmp = sized_rand_bin(packet_size)
    tmp[0] = i[2]
    tmp[4] = i[0]
    sw.in_down = tmp.clone
    sw.run
    puts "#{i}():\t#{sw.in_up.reverse.join}|#{sw.in_down.reverse.join} ==> #{sw.out_up.reverse.join}|#{sw.out_down.reverse.join}"
  }
end
#==========================================================================================
def bf1_output_analyzer in_arr, out_arr, levels
   survivors = []
   in_arr.each { |packet|  packet[-levels..-1] = sized_int2bin 0, levels   }
   out_arr.each { |packet|
     survivors << packet if packet[0].to_s == '1'
   }
   stripped_ret_add = []
   survivors.each {|p|
     tmp = p.clone
     tmp[-levels..-1] = sized_int2bin 0, levels
     stripped_ret_add << tmp
   }

   resched = in_arr - stripped_ret_add
   print "\n//cycle had #{survivors.size} survivors, need to reschedule #{resched.size} packets"
   throw "errr" unless resched.size == in_arr.size - stripped_ret_add.size
#     puts in_arr.inspect
#     puts stripped_ret_add.inspect
#     puts resched.inspect
   return resched

end
#==========================================================================================
def check_packets_buffer packets_buffer
    return false if packets_buffer.size == 0
    packets_buffer.each { |packet|  return true if packet[0].to_s == '1' }
    return false
end
#==========================================================================================
def test_bf_with_random

  srand $my_seed

  require 'set'
  packets_buffer_size = 50
  packets_buffer = Set.new

  data_size = 2
  offset_size = 2
  levels = 4
  packet_size = 2+data_size+levels+offset_size+levels
  bf = Butterfly.new data_size, levels, offset_size
   #generate 50 random packets
   while (packets_buffer_size > packets_buffer.size) do
      candidate = sized_rand_bin(packet_size)
      candidate[-levels..-1] = sized_int2bin 0, levels #ret. ad. is 0
      candidate[0] = '1' #packet is alive
      candidate[1] = '1' #packet is writing
      packets_buffer.add candidate
   end
   #now add the reads
   reads = []
   packets_buffer.each { |packet|
     tmp = packet.clone
     tmp[1]= '0' #packet is reading
     reads << tmp 
   }
   cycle = 0

   packets_buffer = packets_buffer.to_a.concat reads

   while (check_packets_buffer packets_buffer) do
      #get enough packets
      input = packets_buffer[0..2**levels-1]

      bf.in_all = input.clone
      bf.run
      print '#2 in = ' + "#{packet_size*(2**levels)}'b" 
      input.reverse.each { |packet| print packet.reverse.join   }
      print "; \n// cycle(#{cycle}):\t"
      input.reverse.each { |packet| print packet.reverse.join + '|'  }
      print "  \n//         =>\t"
      bf.out_all.reverse.each { |packet| print packet.reverse.join + '|'}
      packets_buffer = (bf1_output_analyzer(input, bf.out_all, levels).concat(packets_buffer[2**levels..-1])).shuffle
      #padding for small buffers  with zeropackets
      (2**levels - packets_buffer.size).times { packets_buffer << sized_int2bin(0, packet_size)}
      print  " new buffer size: #{packets_buffer.size} \n"
      cycle +=1
   end
  puts "//It took #{cycle} cycles to read&write #{packets_buffer_size} packets on a #{2**levels} ports shared memory"
end
#==========================================================================================
def test_bf
  srand $my_seed
  data_size = 2
  offset_size = 2
  levels = 3
  packet_size = 2+data_size+levels+offset_size+levels
  bf = Butterfly.new data_size, levels, offset_size

   (0..15).each { |i|
      input = []
      (2**levels).times {input << sized_rand_bin(packet_size) }

      bf.in_all = input.clone
      bf.run
      print '#2 in = ' + "#{packet_size*(2**levels)}'b"
      input.reverse.each { |packet| print packet.reverse.join   }
      print '; // = '
      input.reverse.each { |packet| print packet.reverse.join + '|'  }
      print ' =>'
      bf.out_all.reverse.each { |packet| print packet.reverse.join + '|'}
      puts ''


  }
end
#==========================================================================================

class Array
  # Shuffle the array
  def shuffle!
    n = length
    for i in 0...n
      r = Kernel.rand(n-i)+i
      self[r], self[i] = self[i], self[r]
    end
    self
  end

  # Return a shuffled copy of the array
  def shuffle
    dup.shuffle!
  end
end


$my_seed = 11676938 #rand(12345678)
puts $my_seed
test_bf_with_random
